Sets

Examples

bdg-secondaryExample 1 The set $V$ of all the vowels in the English alphabet can be written as $V=\{a,e,i,o,u\}$

bdg-secondaryExample 2 The set $O$ of odd odd positive integers less than 10 can be expressed by $O=\{1,3,5,7,9\}$
bdg-primarySet Builder
$O=\{x|x\text{ is an odd positive integer less then 10}\}$
$O=\{x\in\Bbb{Z}^+|x\text{ is an odd and } x<10\}$

bdg-secondaryExample 3 bdg-dangerelements in a set don't necessarily need to share common properties
$\{a,2, Fred, New\ Jersey\}$ is valid set even though the elements have nothing to do with each other

bdg-secondaryExample 4 bdg-dangerellipses ... are used when pattern is obvious
The set of positive integers less than 100 can be denoted by $\{1,2,3,...,99\}$

bdg-secondaryExample 5 bdg-dangersets can contain other sets
The set $\{\Bbb{N},\Bbb{Z},\Bbb{Q},\Bbb{R}\}$ contain 4 elements each of which is a set

Number Sets

$\Bbb{N}=\{0,1,2,3...\}$ = set of all natural numbers

$\Bbb{Z}=\{...,-2,-1,0,1,2,3...\}$ = integers

$\Bbb{N}=\Bbb{Z}^+=\{1,2,3...\}$ = positive integers

$\Bbb{R}=\Set{x\mid x\ \text{can be represented by a decimal expansion}} = \Bbb{Q}\cup \Bbb{Q}^c$ = real numbers

$\Bbb{Q}=\{p/q\mid p, q\in\Bbb{Z},q\neq 0, p\space and\space q\space have\space no\space common\space factors \}$ = rational numbers

$\Bbb{Q}^c=\Bbb{\bar{Q}} =\{x\in \Bbb{R}\mid x\notin\Bbb{Q}\}$ = irrational numbers

$\Bbb{C} =\set{x+ig\mid x,y\in \Bbb{R}\space and\space i^2=-1}$ = Complex numbers

Intervals

&[a,b]=\{\ x\ |\ a\le x\le b\}\textcolor{hotpink}{\text{ closed interval}}\\ &[a,b)=\{\ x\ |\ a\le x\lt b\}\\ &(a,b]=\{\ x\ |\ a\lt x\le b\}\\ &(a,b)=\{\ x\ |\ a\lt x\lt b\}\textcolor{violet}{\text{ open interval}}\\

Equality

Empty Set

There is a special set that has no elements.

We call this the empty set or null set denoted by $\emptyset$

Singleton Set
: A set with one element

$\emptyset\not\equiv\{\emptyset\}$ because thats a singleton set that contains the null set

Venn Diagrams

V . a . e . i . o . u

The universal set is denoted by $⋃$ and is represented by the square of the venn diagram

The universal set contains all possible elements

The set $V$ of all the vowels in the English alphabet can be written as:

V=\{a,e,i,o,u\}

Subsets

Proper Subsets

Remember: $\iff$ means iff replacing the statement if and only if

A\subset B\iff\forall x(x\in A\rightarrow x\in B)\wedge\exists x(x\in B\wedge x\notin A)

Venn Diagram of a Proper Subset

Sets may have other sets as members

Sizes of Set

Let $S$ be a set. If there are exactly $n$ distinct elements in $S$ where $n$ is a nonnegative integer, we say that $S$ is a finite set and that $n$ is the cardinality of $S$ . The cardinality of $S$ is denoted by $|S|$ where $|S| = n$ , we can thus determine that $|\emptyset|=0$

Principle of Inclusion - Exclusion

Let $A$ and $B$ be finite sets
Then $|A\cup B|=|A|+|B| - |A\cap B|$

think it terms of sets so we don't double count for the intersection elements

Extended for more than two sets

| A\cup B \cup C| &= A\cup (B \cup C)|\\ & = |A| + |B\cup C| - |A\cap (B \cup C)|\\ & = |A| + |B| + |C| - |B\cap C| - |A\cap (B \cup C)|\color{yellow}{\text{ use distributive law}} \\ & = |A| + |B| + |C| - |B\cap C| - |(A\cap B)\cup (A\cap C)|\\ & = |A| + |B| + |C| - |B\cap C| - |(A\cap B)\cup (A\cap C)|\\ & = |A| + |B| + |C| - |B\cap C| - ||A\cap B| + |A\cap C| - |(A\cap B)\cap (A\cap C)||\\ & = |A| + |B| + |C| - |B\cap C| - |A\cap B| - |A\cap C| + |A\cap B\cap C|\\

Power Sets

Given a set $S$ , the power set of $S$ is the set of all subsets of the set $S$

The Power set of $S$ is denoted by $\mathcal{P}(S)$
$\mathcal{P}(A)=\Set{B\mid B\subseteq A}$

Cartesian Products

The ordered n-tuple $(a_1,a_2,...,a_n)$ is the ordered collection

We say that $(a_1, ... , a_n) = (b_1,...b_n)\ iff\\$ $a_1 = b_1, a_2 = b_2, ..., a_n = b_n$ or
$\forall (i = 1, 2, ... n) (a_i = b_i)$

Let $A$ and $B$ be sets. The Cartesian product of $A$ and $B$ , denoted $A\times B$ , is the set of all ordered pairs $(a,b)$ , where $a\in A$ and $b\in B$
$A\times B=\Set{(a,b)|a\in A\wedge b\in B}$

The Cartesian product of the sets $A_1,A_2, ... A_n$ denoted by $A_1\times A_2\times ... \times A_n$ is the set of ordered b-tuples $(a_1, a_2, ... , a_n)$ where $a_i$ belongs to $A_i$ for $i=1,2,...,n$

In other words
$A_1\times A_2\times ... \times A_n = \Set{(a_1, a_2, ... , a_n)\mid a_i\in A_i\ for\ i=1,2,...,n}$

bdg-successFact If $|A_i|=m_i$ then
$|A_1x ... xA_n| = m_1 \cdot m_2\cdots m_n = \prod^n_{i=1}m_i$

Set Operations

Union of Sets

Let $A$ and $B$ be sets. The union of these sets, denoted by $A\cup B$ , is the set that contain those elements that are either in $A$ or $B$

$A\cup B=\Set{x|x\in A\lor x\in B}$

Intersection of Sets

Let $A$ and $B$ be sets. The intersection of these sets, denoted by $A\cap B$ , is the set that contains those elements that are in $A$ and $B$

$A\cap B=\Set{x|x\in A\wedge x\in B}$
Two sets called disjoint if there intersection is the empty set
In other words there is no overlap in the Venn Diagram

Difference of Sets

Let $A$ and $B$ be sets. The difference of these sets, denoted by $A-B$ , is the set that contains those elements that are in $A$ but not in $B$

$A-B=\Set{x|x\in A\wedge x\notin B}$

Difference between sets $A$ and $B$ is sometimes denoted by $A\setminus B$

Compliment of Sets

Let $U$ be the universal set. The compliment of a set, denoted by $\bar{A}$ , is the set that contains those elements that are not in $A$ thus $U-A$

$\bar{A}=\Set{x\in U\ |\ x\notin A}$

The compliment depends on what we mean by the universal set $U$

Set Identities

Equivalence	Name
$A\cap U=A$ $A\cup\emptyset =A$	Identity laws
$A\cup U=U$ $A\cap \emptyset =\emptyset$	Domination laws
$A\cup A=A$ $A\cap A=A$	Idempotent laws
$\bar{\bar{A}}=A$ Kind of like double negation* right?*	Complementation law
$A\cup B=B\cup A$ $A\cap B=B\cap A$	Commutative laws
$A\cup(B\cup C)=(A\cup B)\cup C$ $A\cap(B\cap C)=(A\cap B)\cap C$	Associative laws
$A\cup(B\cap C)=(A\cup B)\cap(A\cup C)$ $A\cap(B\cup C)=(A\cap B)\cup(A\cap C)$	Distributive laws
$\overline{A\cap B}=\bar{A}\cup\overline{B}$ $\overline{A\cup B}=\bar{A}\cap\bar{B}$	De Morgan's Laws
$A\cup(A\cap B)=A$ $A\cap(A\cup B)=A$	Absorption laws
$A\cup\bar{A}=U$ $A\cap\bar{A}=\emptyset$	Complement laws

Proof of Demorgan's law for sets

\overline{A\cap B} = \bar{A}\cup\bar{B}

bdg-successProof

\overline{A\cap B} &= \Set{x\in U\mid x\notin(A\cap B)}\\ &= \Set{x\in U\mid \neg(x\in(A\cap B))}\\ &= \Set{x\in U\mid \neg(x\in A \wedge x\in B)}\\ &= \Set{x\in U\mid \neg(x\in A)\lor \neg(x\in B)}\\ &= \Set{x\in U\mid x\notin A\lor x\notin B}\\ &= \Set{x\in U\mid x\in \bar{A}\lor x\in \bar{B}}\\ &= \bar{A}\cup\bar{B}\color{green}{\text{ success!}}\\

bdg-secondaryStatement

\overline{A\cup B} = \bar{A}\cap\bar{B}

bdg-successProof

\overline{A\cap B} &= \Set{x\in U\mid x\notin(A\cup B)}\\ &= \Set{x\in U\mid \neg(x\in(A\cup B))}\\ &= \Set{x\in U\mid \neg(x\in A \lor x\in B)}\\ &= \Set{x\in U\mid \neg(x\in A)\wedge \neg(x\in B)}\\ &= \Set{x\in U\mid x\notin A\wedge x\notin B}\\ &= \Set{x\in U\mid x\in \bar{A}\wedge x\in \bar{B}}\\ &= \bar{A}\cap\bar{B}\color{green}{\text{ success!}}\\

Arbitrary Unions or Intersections

We can define arbitrary unions and intersections for a finite number of sets

A_1\cap A_2\cap\cdots\cap A_n&=\Set{x\mid x\in A_i\text{ for all }i=1,\cdots ,n}\\ A_1\cup A_2\cup\cdots\cup A_n&=\Set{x\mid x\in A_i\text{ for some }i=1,\cdots ,n}\\

Demorgan's Laws become

\overline{A_1\cup A_2\cup\cdots\cup A_n}&=\bar{A_1}\cap \bar{A_2}\cap\cdots\cap \bar{A_n}\\ \overline{A_1\cap A_2\cap\cdots\cap A_n}&=\bar{A_1}\cup \bar{A_2}\cup\cdots\cup \bar{A_n}\\

Set Operations via Bit Strings

Consider $U=\Set{1,2,3,4,5,6,7,8,9,10}$

Each subset of $U$ can be represented as a bit string of length 10, where $A\subseteq U$ is associated to the bit string $Bit_{10}(A)=(b_1,b_2,b_3,b_5,b_4,b_5,b_6,b_7,b_8,b_9,b_{10})$

where $b_i = 1\ if\ i\in A$ and $0\ if\ i\notin A$

For each bit string of length 10 there is a subset of $U$ and for each subset of $U$ there is a bit string of length 10

We say there is a one-to-one corresponded between bitstrings of length 10 and the subsets of a set with 10 elements

$(0,\cdots ,0)\leftrightarrow\emptyset$
$(1,\cdots ,1)\leftrightarrow U$

So if $A=\Set{2,3,7,8,10}$

Bit_{10}(A)=\Set{0,1,1,0,0,0,1,1,0,1}